package code;

import java.util.HashSet;
import java.util.Set;


public class WordSearch {
	
	private int n;
	private int m;
	
	
	private int[][] move={{0,1},{0,-1},{1,0},{-1,0}};
	private int vis[][];
	private int g;
	
    public boolean exist(char[][] board, String word) {
    	n=board.length;
    	m=board[0].length;
    	vis=new int[n][m];
    	
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			g++;
    			if(dfs(i,j,0,board,word))
    				return true;
    		}
    	}
        return false;
    }
    
    public boolean dfs(int x,int y,int index,char[][] board, String word){
    	if(index==word.length()-1 && board[x][y]==word.charAt(index)){
    		return true;
    	}
    	if(vis[x][y]<g && board[x][y]==word.charAt(index)){
    		vis[x][y]=g;
    		for(int i=0;i<4;i++){
    			int s=x+move[i][0];
    			int t=y+move[i][1];
    			if(s>=0 && s<n && t>=0 && t<m && vis[s][t]<g){
    				if(dfs(s,t,index+1,board,word))
    					return true;
    			}
    		}
    		vis[x][y]=g-1;
    	}
    	return false;
    }
    public static void main(String[] args){
    	WordSearch ws=new WordSearch();
//    	char[][] board={{"ABCE"},{"SFES"},{"ADEE"}};
//    	String word="ABCESEEEFS";
//		System.out.println(ws.exist(board, word));
	 }
}
